package com.gorkr.labuladong.data_struct.array;

import org.junit.jupiter.api.Test;

import java.util.PriorityQueue;

/**
 * 数组中第K个最大元素
 *
 * @author gorkr
 * @date 2022/07/23 22:44
 **/
public class M215kthLargestElementInAnArray {

    public int findKthLargest(int[] nums, int k) {
        partition(nums, 0, nums.length - 1);

        return nums[nums.length - k];
    }

    /**
     * @param nums
     * @param i    地位
     * @param j    高位
     * @return 返回被排序元素下标
     */
    private void partition(int[] nums, int i, int j) {
        if (i >= j) {
            return;
        }

        // 要找位置的元素
        int flg = nums[i];

        int low = i;
        int high = j;

        while (low < high) {
            // 因为<=导致没有上界了 对比另一种写法
            while (high > i && nums[high] >= flg) {
                high--;
            }
            while (low < high && nums[low] <= flg) {
                low++;
            }
            // low == high 的时候不交换
            if (low >= high) {
                break;
            }

            int tmp = nums[high];
            nums[high] = nums[low];
            nums[low] = tmp;

        }

        int tmp = nums[low];
        nums[low] = nums[i];
        nums[i] = tmp;

        partition(nums, i, low - 1);
        partition(nums, low + 1, j);
    }


    public int findKthLargest2(int[] nums, int k) {
        int index = nums.length - k;
        return divi(nums, index, partition2(nums, 0, nums.length - 1), 0, nums.length - 1);

    }

    public int divi(int[] nums, int index, int p, int i, int j) {
        if (p == index) {
            return nums[p];
        } else if (p < index) {
            return divi(nums, index, partition2(nums, p + 1, j), p + 1, j);
        } else {
            return divi(nums, index, partition2(nums, i, p - 1), i, p - 1);
        }
    }


    public int findKthLargest3(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num :
                nums) {
            if(pq.size()>=k){
                if(pq.peek()<num){
                    pq.poll();
                    pq.add(num);
                }
            }else {
                pq.add(num);
            }


        }
        return pq.poll();

    }


    private int partition2(int[] nums, int i, int j) {

        // 要找位置的元素
        int flg = nums[i];

        int low = i;
        int high = j;

        while (low < high) {
            // 因为<=导致没有上界了 对比另一种写法
            while (high > i && nums[high] >= flg) {
                high--;
            }
            while (low < high && nums[low] <= flg) {
                low++;
            }
            // low == high 的时候不交换
            if (low >= high) {
                break;
            }

            int tmp = nums[high];
            nums[high] = nums[low];
            nums[low] = tmp;

        }

        int tmp = nums[low];
        nums[low] = nums[i];
        nums[i] = tmp;

        return low;
    }

    @Test
    public void test() {
        int[] mums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(findKthLargest3(mums, 4));
    }
}
    